package bm48;

import java.util.PriorityQueue;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/11 15:47
 * BM48. 数据流中的中位数
 * https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=295&tqId=23457&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    private PriorityQueue<Integer> minQueue = new PriorityQueue<>(); // 小根堆
    private PriorityQueue<Integer> maxQueue = new PriorityQueue<>((x, y) -> (y - x)); // 大根堆

    // 插入操作
    public void Insert(Integer num) {
        if (minQueue.size() == maxQueue.size()) {
            // 如果为偶数个, 则加入到小根堆, 然后将小根堆的堆顶加入到大根堆
            minQueue.offer(num);
            maxQueue.offer(minQueue.poll());
        } else {
            // 如果为奇数个, 则加入到大根堆, 再将大根堆的堆顶加入到小根堆
            maxQueue.offer(num);
            minQueue.offer(maxQueue.poll());
        }
    }

    // 获取中位数
    public Double GetMedian() {
        if (minQueue.size() == maxQueue.size()) {
            return (minQueue.peek() + maxQueue.peek()) / 2.0;
        } else {
            return maxQueue.peek() / 1.0;
        }
    }
}

